package ants;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import cell.Cell;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableSetMultimap;



public class BFS {
  
  public static enum PathDirection {
    BACKWARD, FORWARD
  }
  
  
  public static BFS search(ImmutableSet<? extends Cell> seeds,
                           ImmutableSet<? extends Cell> goals,
                           GameState gameState) {
    return search(seeds, goals, Integer.MAX_VALUE, gameState);
  }
  
  
  public static BFS search(ImmutableSet<? extends Cell> seeds,
                           ImmutableSet<? extends Cell> goals,
                           int depth,
                           GameState gameState) {
    final BFS search = new BFS(seeds, goals, gameState);
    search.ringsBuilder.putAll(0, seeds);
    search.currentDepth = 0;
    search.seen.addAll(seeds);
    for (final Cell seed: seeds)
      search.seededBy.put(seed, seed);
    search.buildAllRingsTo(depth);
    return search;
  }
  
  private int                                                           currentDepth;
  private final GameState                                               gameState;
  
  private final ImmutableSet<? extends Cell>                            goals;
  
  private ImmutableSetMultimap<Cell, Pair<Integer, Cell>>               goalToLengthSeed;
  private final ImmutableSetMultimap.Builder<Cell, Pair<Integer, Cell>> goalToLengthSeedBuilder = ImmutableSetMultimap.builder( );
  
  private ImmutableSetMultimap<Integer, Pair<Cell, Cell>>               lengthToSeedGoal;
  private final ImmutableSetMultimap.Builder<Integer, Pair<Cell, Cell>> lengthToSeedGoalBuilder = ImmutableSetMultimap.builder( );
  
  private ImmutableMap<Cell, Cell>                                      predecessorsOf;
  private final ImmutableMap.Builder<Cell, Cell>                        predecessorsOfBuilder   = ImmutableMap.builder( );
  
  private ImmutableSetMultimap<Integer, Cell>                           rings;
  private final ImmutableSetMultimap.Builder<Integer, Cell>             ringsBuilder            = ImmutableSetMultimap.builder( );
  
  private final Map<Cell, Cell>                                         seededBy                = new HashMap<>( );
  private final ImmutableSet<? extends Cell>                            seeds;
  
  private ImmutableSetMultimap<Cell, Pair<Integer, Cell>>               seedToLengthGoal;
  private final ImmutableSetMultimap.Builder<Cell, Pair<Integer, Cell>> seedToLengthGoalBuilder = ImmutableSetMultimap.builder( );
  
  private final Set<Cell>                                               seen                    = new HashSet<>( );
  
  
  
  
  private BFS(ImmutableSet<? extends Cell> seeds,
              ImmutableSet<? extends Cell> goals,
              GameState gameState) {
    this.gameState = gameState;
    ringsBuilder.putAll(0, seeds);
    this.seeds = seeds;
    this.goals = goals;
    currentDepth = 0;
    seen.addAll(seeds);
    for (final Cell seed: seeds)
      seededBy.put(seed, seed);
  }
  
  
  /**
   * Compute all the rings up to and including ring depth
   * 
   * @param depth
   *          the maximum number of steps to take
   */
  public void buildAllRingsTo(int depth) {
    ImmutableSet<? extends Cell> currentRing = seeds;
    while (currentDepth < depth && !currentRing.isEmpty( ))
      currentRing = buildNextRing(currentRing);
    
    predecessorsOf = predecessorsOfBuilder.build( );
    rings = ringsBuilder.build( );
    lengthToSeedGoal = lengthToSeedGoalBuilder.build( );
    seedToLengthGoal = seedToLengthGoalBuilder.build( );
    goalToLengthSeed = goalToLengthSeedBuilder.build( );
  }
  
  
  private ImmutableSet<? extends Cell> buildNextRing(ImmutableSet<? extends Cell> currentRing) {
    currentDepth++;
    final ImmutableSet.Builder<Cell> nextRingBuilder = ImmutableSet.builder( );
    
    for (final Cell cell: currentRing) {
      final Cell seed = seededBy.get(cell);
      final Collection<Cell> newLandNeighbors = Utils.setDifference(gameState.getLandNeighbors(cell), seen);
      seen.addAll(newLandNeighbors);
      ringsBuilder.putAll(currentDepth, newLandNeighbors);
      nextRingBuilder.addAll(newLandNeighbors);
      for (final Cell neighbor: newLandNeighbors) {
        seededBy.put(neighbor, seed);
        predecessorsOfBuilder.put(neighbor, cell);
        
        // Have we reached a goal?
        final Cell neighborAsGoal = contains(goals, neighbor);
        if (neighborAsGoal != null) {
          lengthToSeedGoalBuilder.put(currentDepth, new Pair<Cell, Cell>(seed, neighborAsGoal));
          seedToLengthGoalBuilder.put(seed, new Pair<Integer, Cell>(currentDepth, neighborAsGoal));
          goalToLengthSeedBuilder.put(neighborAsGoal, new Pair<Integer, Cell>(currentDepth, seed));
        }
      }
    }
    
    final ImmutableSet<? extends Cell> nextRing = nextRingBuilder.build( );
    if (nextRing.isEmpty( )) currentDepth--;
    return nextRing;
  }
  
  
  private Cell contains(ImmutableSet<? extends Cell> cells, Cell match) {
    for (final Cell cell: cells)
      if (cell.equals(match)) return cell;
    return null;
  }
  
  
  public int getCurrentDepth( ) {
    return currentDepth;
  }
  
  
  public Direction getFirstStep(Cell endCell, PathDirection backward) {
    final ImmutableList<Cell> path = backward.equals(PathDirection.FORWARD) ? pathTo(endCell) : pathBackFrom(endCell);
    return Direction.getDirections(path.get(0), path.get(1)).get(0);
  }
  
  
  public ImmutableSetMultimap<Cell, Pair<Integer, Cell>> getGoalToLengthSeed( ) {
    return goalToLengthSeed;
  }
  
  
  
  public ImmutableSetMultimap<Integer, Cell> getInversePathLengths( ) {
    return rings;
  }
  
  
  public ImmutableSetMultimap<Integer, Pair<Cell, Cell>> getLengthToSeedGoal( ) {
    return lengthToSeedGoal;
  }
  
  
  public ImmutableSetMultimap<Cell, Integer> getPathLengths( ) {
    return getInversePathLengths( ).inverse( );
  }
  
  
  public ImmutableMap<Cell, ? extends Cell> getSeededBy( ) {
    return ImmutableMap.copyOf(seededBy);
  }
  
  
  public ImmutableSetMultimap<Cell, Pair<Integer, Cell>> getSeedsToLengthGoal( ) {
    return seedToLengthGoal;
  }
  
  
  public ImmutableList<Cell> pathBackFrom(Cell end) {
    return pathTo(end).reverse( );
  }
  
  
  /**
   * A good illustration of using a Builder during the construction stage and
   * converting it to an immutable at the end.
   * 
   * The object keeps only the predecessors Builder. Whenever a path is needed,
   * build() is called, and the predecessors Map is then used to build a path.
   * 
   * @param end
   * @return
   */
  public ImmutableList<Cell> pathTo(Cell end) {
    return pathToBuilder(end).build( );
  }
  
  
  private ImmutableList.Builder<Cell> pathToBuilder(Cell end) {
    
    return predecessorsOf.keySet( ).contains(end) ? pathToBuilder(predecessorsOf.get(end)).add(end)
                                                 : ImmutableList.<Cell> builder( ).add(end);
  }
  
  
  @Override
  public String toString( ) {
    return "Search<" + getCurrentDepth( ) + ">:" + toString(rings);
  }
  
  
  private String toString(ImmutableSetMultimap<Integer, Cell> rings) {
    final StringBuilder sb = new StringBuilder( );
    for (final Entry<Integer, Collection<Cell>> entry: rings.asMap( ).entrySet( ))
      sb.append("\n\t\t\t")
        .append(entry.getKey( ))
        .append(" -> ")
        .append(entry.getValue( ));
    return sb.toString( );
  }
}
